%!TEX program = xelatex
% 完整编译方法 1 pdflatex -> bibtex -> pdflatex -> pdflatex
% 完整编译方法 2: xelatex -> bibtex -> xelatex -> xelatex
\documentclass[lang=cn,11pt]{elegantpaper}

\title{凸优化}
\author{eleve11}

% \institute{\href{https://elegantlatex.org/}{Elegant\LaTeX{} 项目组}}

% 不需要版本信息，直接注释即可
% \version{0.07}
% 不需要时间信息的话，需要把 \today 删除。
\date{\today}


% 如果想修改参考文献样式，请把这行注释掉
\usepackage[authoryear]{gbt7714}  % 国标

\begin{document}

\maketitle

% \begin{abstract}
% \end{abstract}

\section{凸优化}
经常看到ML相关论文里总会出现某个优化函数是凸的，也即是个凸函数，这总意味着这个函数性质很好，优
化会很容易。但是笔者对凸优化只停留在知道它的存在，而其他就不是十分清楚。这篇笔记也是让自己对
凸优化有个基本的了解。\\
\indent 在读凸优化的第一章时，作者说明了识别一个问题是否为凸优化问题，以及是否可以转化为凸优
化问题是具有挑战性的工作。但是一旦问题可以转化为凸优化问题，面对数百个变量，上千个约束条件，使
用计算机求解此问题非常快。作者也是期望读者去具备一种识别与表述凸优化问题的技巧。\\
\indent 阅读之前确保自己的\textbf{离散数学}知识没有忘记。


\section{线性规划与凸优化}
首先是对概念性问题来个了解。\\
\indent \textbf{数学优化问题}：数学优化问题可以写成如下形式：
\begin{align} \label{formula:optimize}
    \textrm{minimize} & \quad f_0(x) \\
    \textrm{subject to} & \quad f_i(x) \leq b_i, \qquad i=1, 2, \ldots, m.
\end{align}
这里，向量$x=(x_1, \ldots, x_n)$称为问题的优化变量，函数$f_0: \Re ^n \rightarrow \Re$
称为目标函数。函数$f_0: \Re ^n \rightarrow \Re, i=1, 2, \ldots, m$称为约束函数，常数
$b_1, \ldots, b_m$称为约束上限或约束边界，如果在所有满足约束条件的向量中向量$x^*$对应的目
标函数值最小：即对任意满足约束$f_1(z) \leq b_1,\ldots,f_m(z) \leq b_m$的向量$z$，有
$f_0(z) \geq f_0(x^*)$，那么称$x^*$为式子\ref{formula:optimize}的最优解或者解。\\
\indent \textbf{线性规划}是具有特殊形式的目标函数和约束函数的优化问题的一类，若问题
\ref{formula:optimize}中的目标函数与约束函数$f_0,\ldots,f_m$都是线性函数，即对任意的
$x, y \in \Re^n$和$\alpha,\beta \in \Re$有
\begin{equation} \label{formula:lqo}
    f_i(\alpha x + \beta y) = \alpha f_i(x) + \beta f_i(y)
\end{equation}
则此优化问题称之为线性问题，若优化问题不是线性的，则称为非线性规划。 \\
\indent 而凸优化问题中的目标函数与约束函数都是凸函数，即对于任意$x, y \in \Re^n$和
$\alpha,\beta \in \Re$且满足$\alpha + \beta = 1, \alpha \geq 0, \beta \geq 0$，下
述不等式成立
\begin{equation} \label{formula:lnqo}
    f_i(\alpha x + \beta y) \leq \alpha f_i(x) + \beta f_i(y)
\end{equation}
比较\ref{formula:lqo}和\ref{formula:lnqo}，可以知道凸优化为性质更为一般的线性规划。线性
规划需要更严格的满足等式，凸函数只需要在$\alpha$和$\beta$在去特定值的情况下满足不等式。

\section{凸集}
    在上节的基础上，假设在空间$\Re ^n$中，有这样直线满足：
    \begin{equation*}
        y= \theta x_1 + (1 - \theta)x_2
    \end{equation*}
    其中满足条件的点组成了一组穿过$x_1$和$x_2$的直线，如图\ref{fig:cvxline}，其中在直线
    的加粗段为$0 \leq \theta \leq 1$
    \begin{figure}[htbp]
      \centering
      \includegraphics[width=0.6\textwidth]{cvxline.png}
      \caption{\label{fig:cvxline}}
    \end{figure}
    \subsection{仿射集}
    \indent 如果通过集合$C \subseteq \Re ^n$中任意两个不同点的直线仍然在集合$C$中，则称
    集合$C$是\textbf{仿射}的，等价于对于任意$x_1, x_2 \in C$及$\theta \in \Re$有
    $\theta x_1 + (1 - \theta)x_2 \in C$ \\
    \indent 将概念拓展到多个点上，如果$\theta _1 + \ldots + \theta _k=1$，我们称具有
    形式$\theta_1 x_1 + \ldots + \theta_k x_k$的点为$x_1, \ldots, x_k$的
    \textbf{仿射组合}，有集合$C \subseteq \Re ^n$中的点的所有仿射组合组成的集合称为集合
    $C$的\textbf{仿射包}，记为$\textrm{\textbf{aff}}C$
    \begin{displaymath}
        \textrm{\textbf{aff}} C = \{ \theta_1 x_1 + \ldots + \theta_k x_k |
        x_1, \ldots, x_k \in C,
        \theta _1 + \ldots + \theta _k=1 \}
    \end{displaymath}
    仿射包是包含$C$的最小的仿射集合，也就是说：如果$S$是满足$C \subseteq S$的仿射集合，
    那么$\textrm{\textbf{aff}} C \subseteq S$。\\
    \indent 集合$C$的\textbf{仿射维数}为仿射包的维数，如果集合$C \subseteq \Re^n$的
    仿射维数小于n，那么这个集合在仿射集合$\textrm{\textbf{aff}} C \neq \Re^n$中。我们
    定义集合$C$的\textbf{相对内部}为$\textrm{\textbf{aff}} C$的内部，记为
    $\textrm{\textbf{relint}}C$，即
    \begin{displaymath}
        \textrm{\textbf{relint}}C=\{ x \in C | B(x,r) \cap
         \textrm{\textbf{aff}}C \subseteq C \textrm{对于某些}r >0 \}
    \end{displaymath}
    其中$B=(x,r)=\{ y| \| y-x \| \leq r \}$，即半径为r，中心为x并由范数
    $\| \cdot \|$定义的球，于是定义集合C的\textbf{相对边界}为
    $\textrm{\textbf{cl}}C \ \textrm{\textbf{relint}}C$，
    $\textrm{\textbf{cl}}C$表示C的闭包。
    \subsection{子空间}
    在凸优化书中的子空间，与我想象的子空间不同，我所认为的子空间是一个降维后的空间，或者一个
    局部的空间。\\
    如果C是一个仿射集合并且$x_0 \in C$，则集合
    \begin{displaymath}
        V = C - x_0 = {x-x_0 |x \in C}
    \end{displaymath}
    是一个子空间，即加法与乘法是封闭的(对某个集合的成员进行一种运算，生成的仍然是这个集合的
    成员，则称该集合在这个运算下闭合)。\\
    \indent 仿射集合也可以表示为
    \begin{displaymath}
        C = V + x_0 = {v+x_0 |v \in V}
    \end{displaymath}
    即子空间加一个偏移。与仿射集合C相关联的子空间V与$x_0$的选取无关，$x_0$可以是C中的任意
    一点。定义仿射集合C的维数为子空间$V=C-x_0$的维数。
    \subsection{凸集}
    \indent 集合$C$被称为\textbf{凸集}，如果$C$中任意两点间的线段仍在$C$中，即对于任意的
    $x_1,x_2 \in C$和满足$0 \leq \theta \leq 1$的$\theta$都有
    \begin{equation*}
        \theta x_1 + (1 - \theta)x_2 \in C
    \end{equation*}
    如图\ref{fig:cvx},左图为凸集，右图为非凸集。
    \begin{figure}[htbp]
      \centering
      \includegraphics[width=0.7\textwidth]{cvx.png}
      \caption{\label{fig:cvx}}
    \end{figure}
    集合$C$中所有的凸组合组成的集合称为\textbf{凸包}，记为$\textrm{\textbf{conv}}C$:
    \begin{displaymath}
        \textrm{\textbf{conv}}C=\{\theta_1 x_1 + \ldots + \theta_k x_k |
        x_i \in C, \theta_i \geq 0, i=1, \ldots, k,
        \theta _1 + \ldots + \theta _k=1 \}
    \end{displaymath}
    \subsection{锥}
    如果对于任意$x \in C$和$\theta \geq 0$都有$\theta x \in C$， 我们称集合C为
    \textbf{锥}或\textbf{非负齐次}。如果集合C是锥，并且是凸的，则称C为\textbf{凸锥}，
    即对于任意$x_1,x_2 \in C$和$theta_1,theta_2 \geq 0$都有
    \begin{displaymath}
        \theta_1 x_1 + \theta_2 x_2 \in C
    \end{displaymath}
    具有$\theta_1 x_1 + \ldots + \theta_k x_k, theta_1,\ldots,\theta_k \geq 0$
    形式的点称为$x_1,\ldots,x_k$的\textbf{锥组合}(或者\textbf{非负线性组合})。如果
    $x_i$均属于凸锥，那么$x_i$的每一个锥组合也在C集合中。\\
    \indent 集合C的锥包是C中元素的所有锥组合的集合，即
    \begin{displaymath}
        \{ \theta_1 x_1 + \ldots + \theta_k x_k | x_i \in C, \theta_i \geq 0,
         i=1, \ldots, k, \}
    \end{displaymath}
    它是包含C的最小的凸锥。
    \subsection{认定的一些例子}
    空集，任意一个点${x_0}$、全空间$\Re^n$都是$\Re^n$的仿射(自然也是凸的)子集。 \\

% \nocite{*}

% 如果想修改参考文献样式（非国标），请把下行取消注释，并换成合适的样式（比如 unsrt，plain 样式）。
%\bibliographystyle{aer}
% \bibliography{wpref}
\newpage
\begin{thebibliography}{99}
    \bibitem{b} S.boyd等著,王书宁等译. 凸优化 (2013)
    \bibitem{ba} S.boyd, L.Vandenberghe. Convex Optimization (2009)
\end{thebibliography}

\end{document}
